
\section{Graph Theory and Matrix Theory Review }

In this section, some basic concepts of the graph theory and matrix
theory will be introduced. They are used in the analysis of convergence
or performance of consensus algorithm. Because consensus algorithm
actually relates to a matrix iteration algorithm, it is necessary
to introduce some of these theorems. For full information about matrix
theory, see \cite{Varga2010}, and the work \cite{Russell1994} states
more details about Laplacian matrix. However, some useful properties
of Laplacian matrix will to be introduced here. 

Let ${\cal G}=\left({\cal V},{\cal E},{\cal A}\right)$ be a graph
with $n$ nodes. The in-degree and out-degree of node $i$ are defined
by:

\begin{equation}
D_{in}\left(i\right)=\sum_{i=1}^{n}a_{i,j}
\end{equation}
\begin{equation}
D_{out}\left(i\right)=\sum_{j=1}^{n}a_{i,j}
\end{equation}
where $a_{i,j}$ is the elements of matrix ${\cal A}$. This definition
states that in-degree of node $i$ is the $i^{th}$ column sum of
matrix ${\cal A}$ and the out-degree of node $i$ is the $i^{th}$
row sum of matrix ${\cal A}.$ And the graph Laplacian matrix ${\cal L}$
induced by the ${\cal G}$ is the same as defined before, see \ref{eq:Graph Laplacian def.}.
In addition, we can find the relationship of ${\cal L}$ and ${\cal A}$.
\begin{equation}
{\cal L}=\Delta-{\cal A}
\end{equation}
 where $\Delta$ is a diagonal matrix $\Delta=\left[\Delta_{i,j}\right]$,
$\Delta_{i,j}=0$ for all $i\neq j$ and $\Delta_{ii}=D_{out}\left(i\right)$.

Note that we assume the diagonal elements $a_{i,i}$ of matrix ${\cal A}$
equal to zero for all $i$. Thus, the Laplacian matrix is only dependent
on the off-diagonal elements of ${\cal A}$. Moreover, if we assume
matrix ${\cal A}$ is non-negative, we can benefit from the properties
of non-negative matrix, and use them in optimization of convergence
rate of consensus algorithm.


\subsection{Irreducibility and Strong Connected Graph.}

For an undirected graph, the consensus $\mathbf{x}^{*}$ can be achieved
if and only if the graph is connected. (Note that the consensus is
a stable state of the system dynamic. For the average consensus problem
the consensus state is a state where all the network node converge
to the global average.) But for the directed graph, this condition
of achieving consensus becomes into if and only if the graph is strongly
connected. 

A directed graph is strongly connected if and only if for any two
distinct nodes $i$ and $j$, there exists a path that follows the
direction of the edges and connects $i$ and $j$ on the digraph. 
\begin{defn}
\label{Def.Irreducebility}for $n>1$, an $n\times n$ matrix $A\in R^{n\times n}$
is reducible if there exists an $n\times n$ permutation matrix $P$
such that $PAP^{T}$ is in block upper triangular form. 
\begin{equation}
PAP^{T}=\left[\begin{array}{cc}
A_{1,1} & A_{1,2,}\\
O & A_{2,2}
\end{array}\right]
\end{equation}
where $A_{1,1}$ is an $r\times r$ submatrix and $A_{2,2}$ is an
$\left(n-r\right)\times\left(n-r\right)$ submatrix, and $O$ is an
null matrix, $1\leq r<n$. If no such a permutation matrix exists,
the matrix $A$ is irreducible. If $n=1$, then $A$ is reducible
if $A=0$, and irreducible otherwise. 
\end{defn}
The relationship of the irreducible property of matrix $A$ and the
strong connected property of directed graph ${\cal G}\left(A\right)$
is stated by the following theorem.
\begin{thm}
An $n\times n$ complex matrix $A\in C^{n\times n}$ is irreducible
if and only if its directed graph ${\cal G}\left(A\right)$ is strongly
connected. \cite{Varga2010}
\end{thm}
The proof of this theorem is obvious. If a graph is strongly connected,
all the off diagonal elements of graph matrix $A$ cannot be vanished
by matrix permutation. Therefore, matrix $A$ doesn't exists the block
upper triangular form as given in Def. \ref{Def.Irreducebility}. 


\subsection{Spectral radius of a matrix}

Spectral radius of a matrix is one of the basic concepts in the matrix
iteration theory. It is defined by the largest eigenvalue of the matrix.
The matrix iteration is very useful in many applications, denoted
by $A,A^{2},A^{3},\ldots$. The power sequence is said to be convergent,
if and only if $\lim_{k\to\infty}A^{k}=O$, where $O$ is a zero matrix
with all zero entries. The following theorem states that the convergent
property is strongly connected with the spectral radius. 
\begin{thm}
\label{thm:Convergent <=00003D> p(A)<1} if $A\in C^{n\times n}$
is an $n\times n$ complex matrix, then $A$ is convergent if and
only if $\rho\left(A\right)<1.$\end{thm}
\begin{proof}
The proof uses the Jordan form of a matrix. For any matrix $A\in C^{n\times n}$,
there exists a nonsingular $n\times n$ matrix $T$, such that $A$
reduces into the Jordan normal form 
\begin{equation}
T^{-1}AT=J=\left[\begin{array}{cccc}
J_{1} &  &  & O\\
 & J_{2}\\
O &  & \ddots & J_{m}
\end{array}\right]
\end{equation}
 where each Jordan block $J_{i}$ is an $r_{i}\times r_{i}$ submatrix
in the form 
\begin{equation}
J_{i}=\left[\begin{array}{ccccc}
\lambda_{i} & 1\\
 & \lambda_{i} & 1\\
 &  & \lambda_{i} & \ddots\\
 &  &  & \ddots & 1\\
 &  &  &  & \lambda_{i}
\end{array}\right]
\end{equation}
Thus, the matrix $J$ and $A$ are similar and have the same eigenvalues
$\lambda_{i},i=1,\ldots m$

A direct computation of the power iteration of matrix $A$ will give
us the following equation
\[
A^{k}=TJ^{k}T^{-1}=T\left[\begin{array}{cccc}
J_{1}^{k} &  &  & O\\
 & J_{2}^{k}\\
O &  & \ddots & J_{m}^{k}
\end{array}\right]T^{-1}
\]
because the property of Jordan block, the power of each Jordan block
will have the form
\[
J_{i}^{2}=\left[\begin{array}{ccccc}
\lambda_{i}^{2} & 2\lambda_{i} & 1\\
 & \lambda_{i}^{2} & 2\lambda_{i} & \ddots\\
 &  & \lambda_{i}^{2} & \ddots & 1\\
 &  &  & \ddots & 2\lambda_{i}\\
 &  &  &  & \lambda_{i}^{2}
\end{array}\right],\mbox{if }r_{i}\geq3
\]
 and more generally, let $J_{i}^{k}=\left[c_{m,n}\left(i,k\right)\right]$,
$1\leq m$, $n\leq r_{i}$, and it has 
\[
c_{m,n}\left(i,k\right)=\begin{cases}
0 & n<m\\
\left(\begin{array}{c}
k\\
n-m
\end{array}\right)\lambda_{i}^{k-n+m} & m\leq n\leq\min\left(r_{i},k+m\right)\\
0 & k+m<n<r_{i}
\end{cases}
\]
 Since $\rho\left(A\right)<1$, and matrix $J$ share the same eigenvalues
with $A$, $\left|\lambda_{i}\right|<1$. This lead to $\lim_{k\to\infty}c_{m,n}\left(i,k\right)=0,\:\mbox{for all }1\leq m\leq r_{i},1\leq n\leq r_{i}$,
so that the each Jordan block is convergent. Therefore, the matrix
iteration $A^{k}=TJ^{k}T^{-1}$ is also convergent. This completes
the proof. 
\end{proof}
We give the proof of \prettyref{thm:Convergent <=00003D> p(A)<1}
here as it will be very useful in the proof of an convergence conditions
theorem for distributed consensus algorithm, see \prettyref{sub:DT-First-Order-DAC}.
At the same time, the Jordan normal form weight matrix $W^{k}=TJ^{k}T^{-1}$
gives the local value vector $\mathbf{x}\left(k\right)=W^{k}\mathbf{x}\left(0\right)$
another expression in terms of eigenvalues and eigenvectors, which
reflects the basic ideas of the finite-time consensus algorithm. This
will be introduced in \prettyref{sec:Finite-Time-Distributed-Consensu}. 


\subsubsection{Gerschgorin's theorem}

The calculation of eigenvalues a matrix $A$ involves determination
of the matrix $\lambda I-A$ and solving a high order polynomial equation.
In some situations, for example, when the matrix dimension is very
large, it is very difficult to determine the spectral radius precisely.
However, the following theorem of Gerschgorin provides an upper bound
of the spectral radius \cite{Horn1990}.
\begin{thm}
Let $A=\left(a_{i,j}\right)$ be an arbitrary $n\times n$ matrix.
Denote the 
\begin{equation}
d_{i}=\sum_{j=1,j\neq i}^{n}\left|a_{i,j}\right|
\end{equation}
then all the eigenvalues of matrix $A$ are lie in the union of the
disks.
\begin{equation}
\left|z-a_{i,i}\right|\leq d_{i},\ 1\leq i\leq n.
\end{equation}

\end{thm}
The above theorem is well-known, so the proof is omit here. But the
theorem immediately give the result of
\begin{cor}
\label{cor:Upper Bound of p(A)}Let $A=\left(a_{i,j}\right)$ be an
arbitrary $n\times n$ matrix, and 
\begin{equation}
v=\max_{1\leq i\leq n}\sum_{j=1}^{n}\left|a_{i,j}\right|
\end{equation}
then we have $\rho\left(A\right)\leq v$. 
\end{cor}
Therefore, the maximum of the row sums of the modular of the entries
of matrix $A$ provides a upper bound for spectral radius $\rho\left(A\right)$.
Since $A$ and $A^{T}$ have the same eigenvalues, applying the \ref{cor:Upper Bound of p(A)}
to $A^{T}$ will lead to 
\begin{cor}
Let $A=\left(a_{i,j}\right)$ be an arbitrary $n\times n$ matrix,
and 
\begin{equation}
v'=\max_{1\leq j\leq n}\sum_{i=1}^{n}\left|a_{i,j}\right|
\end{equation}
then we have $\rho\left(A\right)\leq v'$.
\end{cor}
As both the row sum and column sum of the modular of the entries of
matrix can provide the upper bound for $\rho\left(A\right)$, the
minimum of $v$ and $v'$ gives the better upper bound. 



Just as we assume before, the adjacent matrix ${\cal A}$ of the graph
${\cal G}$ is non-negative, which means all elements are non-negative.
Then, the induced graph Laplacian matrix will have the following result
using the Gerschgorin's theorem. 




\subsubsection{Perron-Frobenius Theorem}

The Perron-Frobenius theorem states that if matrix $A$ is nonnegative
and irreducible which means the digraph of matrix A is strongly connected,
the spectral radius $\rho(A)$ is equal to a simple eigenvalue of
$A$ associated with a positive eigenvector \cite{Piziak2007}. The
details of Perron-Frobenius is as follows.
\begin{thm}
\label{thm:Perron-Frobenius thm.} Let $A$ be an $n\times n$ and
irreducible matrix with non-negative and real numbers as its entries.
Then, \end{thm}
\begin{enumerate}
\item $A$ has a positive real eigenvalue equal to its spectral radius $\rho\left(A\right)$.
\item $\rho\left(A\right)$ is a simple eigenvalue of $A$.
\item To the eigenvalue $\rho\left(A\right)$, the corresponding eigenvector
is positive, i.e. $\mathbf{x}>\mathbf{0}$.
\item $\rho\left(A\right)$ increases if any entry of $A$ increases.
\end{enumerate}
Recall the problem of finding the bounds for the spectral radius,
the Perron-Frobenius theorem provides the nontrivial lower-bound of
$\rho\left(A\right)$. In the \prettyref{cor:Upper Bound of p(A)},
the nontrivial upper bound of $\rho\left(A\right)$ is found. Together
with these two results, we can have a conclusion of the spectral radius
of a non-negative and irreducible matrix given in the following.
\begin{lem}
If $A=\left[a_{i,j}\right]$ is an $n\times n$ non-negative and irreducible
matrix, then either 
\begin{equation}
\sum_{j=1}^{n}a_{i,j}=\rho\left(A\right),\mbox{for all }1\leq i\leq n,
\end{equation}
or 
\begin{equation}
\min_{1\leq i\leq n}\left(\sum_{j=1}^{n}a_{i,j}\right)<\rho\left(A\right)<\max_{1\leq i\leq n}\left(\sum_{j=1}^{n}a_{i,j}\right).
\end{equation}
\end{lem}
\begin{thm}
Let $A=\left[a_{i,j}\right]$ be an $n\times n$ non-negative and
irreducible matrix, for any $\mathbf{x}>\mathbf{0}$, either
\begin{equation}
\min_{1\leq i\leq n}\left(\frac{\sum_{j=1}^{n}a_{i,j}x_{j}}{x_{i}}\right)<\rho\left(A\right)<\max_{1\leq i\leq n}\left(\frac{\sum_{j=1}^{n}a_{i,j}x_{j}}{x_{i}}\right)
\end{equation}
or 
\begin{equation}
\frac{\sum_{j=1}^{n}a_{i,j}x_{j}}{x_{i}}=\rho\left(A\right),\ \mbox{for all }1\leq i\leq n.
\end{equation}
Moreover,
\begin{equation}
\max_{\mathbf{x}\in P}\min_{1\leq i\leq n}\left(\frac{\sum_{j=1}^{n}a_{i,j}x_{j}}{x_{i}}\right)=\rho\left(A\right)=\min_{\mathbf{x}\in P}\max_{1\leq i\leq n}\left(\frac{\sum_{j=1}^{n}a_{i,j}x_{j}}{x_{i}}\right)
\end{equation}

\end{thm}
The equality is valid if we choose the $\mathbf{x}$ equal to the
positive eigenvector $e>0$ corresponding to the eigenvalue $\rho\left(A\right)$.
The method shown above will be applicable, because it provides us
both the upper bounds and lower bounds for the spectral radius of
a non-negative and irreducible matrix, by a simple algorithm without
calculating the determination of $\lambda I-A$. 




\subsection{Diagonalizable matrix \& Symmetric matrix}

The Jordan normal form of weight matrix $W^{k}=TJ^{k}T^{-1}$ gives
the local value vector $\mathbf{x}\left(k\right)=W^{k}\mathbf{x}\left(0\right)$
an analitical expression in terms of eigenvalues and eigenvectors.
Moreover, if the matrix $W$ is symmetric, the expressions of $\mathbf{x}\left(k\right)$
can be simplified. Then, algorithms such as the finite-time consensus,
can be implemented more easily. In addition, under the the assumption
of symmetric weight matrices, the optimal weight matrix which has
the fastest convergence rate can be found through a semi-definite
problem. \cite{Li2010}. 
\begin{defn}
A matrix $A$ is diagonalized, if and only if there exist a nonsigular
matrix $T$, which reduce $A$ into the form 
\[
T^{-1}AT=\mbox{diag}\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\right)
\]

\end{defn}
Generally, a matrix are diagonalized by an unitary matrix if and only
if it is normal. Normal matrix $A$ means it satisfies $A^{H}A=AA^{H}$.
Let $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ be the eigenvalues
of $A$. There exists a unitary matrix $U$, which satisfies $U^{H}=U^{-1}$,
such that $U^{-1}AU=\mbox{diag}\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\right)$.
For real normal matrix $A$, if all of its eigenvalues are real, there
exists an orthogonal matrix $P,$ which has $P^{T}=P^{-1}$, reduces
the real matrix $A$ into diagonalized form $P^{-1}AP=\mbox{diag}\left(\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\right)$. 

Specificlly, any real nonsigular symmetric matrix $A\in R^{n\times n}$
has $n$ linearly independent real eigenvectors. Moreover, these eigenvectors
can be chosen so that they are orthogonal to each other with modular
one. Thus, the real symmetric matrix can be decomposed by an orthogonal
matrix $P$, i.e. $A=P\Lambda P^{-1}$, where $\Lambda$ is a diagonal
matrix whose entries equal to the eigenvalues of $A$. Also the symmetric
matrix has all its eigenvalues algebra multiplicity equal to the gerometric
multiplicity, so all the Jordan block have size one.
